package afeng.world.pangu.算法;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @description:
 * @author: liqf
 * @create: 2021-08-24 08:54
 **/
public class 二叉查找 {

    /**
     *
     * @param arr 数组
     * @param i 目标值
     * @param leftIdx 坐坐标
     * @param rightIdx 右坐标
     * @return 得到的坐标
     */
    private int searchDubKey(int[] arr, int i,int leftIdx,int rightIdx) {
//        int rightIdx = arr.length - 1;
//        int leftIdx =

        int probablyMid = (leftIdx+rightIdx)/2; //滑中间坐标

        // todo 方法二, 此处居然可以用循环!!! while(left<right) 逼近法
        //

        if (arr[probablyMid]>i){ //前半段
            probablyMid = searchDubKey(arr, i, leftIdx, probablyMid);
        }
        if(arr[probablyMid]<i){ //后半段
            probablyMid = searchDubKey(arr, i, probablyMid, rightIdx);
        }
        return probablyMid;

    }
    @Test
    void name() {
//        int[] arr = {10,20,30,50,100, 120,200, 300,333};
        int[] arr = {10,20,30,50,100,111, 120,200, 300,333};
        int num = searchDubKey(arr,199,0,arr.length-1);
        System.out.println("num = " + num);
        System.out.println("arr[num] = " + arr[num]);
    }

    @Test
    void search() {
        int[] arr = {10,20,30,50,100,111, 120,200, 300,333};
        int i = Arrays.binarySearch(arr, 200); // 是否包含200, 若包含在那个位置
        System.out.println("i = " + i);
    }
}

